// https://www.lintcode.com/problem/matrix-zigzag-traversal/

public class Solution {
    /**
     * @param matrix: An array of integers
     * @return: An array of integers
     */
    public int[] printZMatrix(int[][] matrix) { // Python版本有bug，纯属歪打正着。
        // write your code here
        int rows = matrix.length, cols = matrix[0].length;
        int[] ret = new int[rows * cols];
        int i = 1, r = 0, c = 0, count = rows * cols;
        ret[0] = matrix[0][0];
        while (i < count) {
            if (c < (cols - 1)) { // 向右
                ++c;
                ret[i] = matrix[r][c];
                ++i;
            }
            else if (r < (rows - 1)) { // 不能向右就向下
                ++r;
                ret[i] = matrix[r][c];
                ++i;
            }
            while ((i < count) && (r < (rows - 1)) && (c > 0)) { // 左下
                ++r;
                --c;
                ret[i] = matrix[r][c];
                ++i;
            }
            if ((i < count) && (r < (rows - 1))) { // 向下
                ++r;
                ret[i] = matrix[r][c];
                ++i;
            }
            else if ((i < count) && (c < (cols - 1))) { // 向右
                ++c;
                ret[i] = matrix[r][c];
                ++i;
            }
            while ((i < count) && (r > 0) && (c < (cols - 1))) { // 右上
                --r;
                ++c;
                ret[i] = matrix[r][c];
                ++i;
            }
        }
        return ret;
    }
}